Abstract: Motivated by cryptography, quantum information theory, circuit complexity, and derandomization, there has been significant recent progress in the study of random permutations resembling a completely random permutation of $n$-bit strings. Of particular interest is the case where the measure of "resemblance" is approximation of the $k$-th moments of the matrix representations. Such random permutations are known as approximate $k$-wise independent permutations.
In this talk I will discuss some recent results that show that small random reversible circuits compute approximate $k$-wise independent permutations:
i) We show that a random reversible circuit with $\tilde{O}(nk)$ gates computes a constant-approximate $k$-wise independent permutation. This result implies a generalization of Shannon's circuit lower bound argument.
ii) We show that a random reversible circuit with $\tilde{O}(nk^2)$ layers of 1D-local gates arranged in a brickwork architecture computes a exp($-nk$)-approximate $k$-wise independent permutation; connections to block ciphers exist.
Based on joint works with William Gay (CMU), Lucas Gretta (Berkeley), Nicholas Kocurek (CMU), Ryan O'Donnell (CMU), Angelos Pelecanos (Berkeley).